package binaryTree.ClosestCommonAncestor;

import binaryTree.TreeNode;

public class Class1644 {
    boolean foundP,foundQ=false;
    TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        TreeNode res = find(root, p.val, q.val);
        if (!foundP || !foundQ) {
            return null;
        }
        // p 和 q 都存在二叉树中，才有公共祖先
        return res;
    }

    public TreeNode find(TreeNode root,int p,int q){
        if ( root==null){
            return  null;
        }
        if (root.val==p||root.val==q){
            return  root;
        }

        TreeNode left = find(root.left, p, q);
        TreeNode right = find(root.right, p, q);
        if (left!=null&&right!=null){
            return  root;
        }
        if (root.val==p||root.val==q){
            if (root.val==p){
                foundP=true;
            }
            if (root.val==q){
                foundQ=true;
            }
        }

        return left!=null?left:right;

    }



}
